
class Matrix:
	def __init__(self, rows):
		self.rows = rows

	def copy(self):
		res = []
		for i in range(len(self.rows)):
			row = []
			res.append(row)
			for j in range(len(self.rows[i])):
				row.append(self.rows[i][j])
		return Matrix(res)

	def __add__(self, other):
		res = []
		for i in range(len(self.rows)):
			row = []
			res.append(row)
			for j in range(len(other.rows[0])):
				row.append(self.rows[i][j] + other.rows[i][j])
		return Matrix(res)

	def __sub__(self, other):
		res = []
		for i in range(len(self.rows)):
			row = []
			res.append(row)
			for j in range(len(other.rows[0])):
				row.append(self.rows[i][j] - other.rows[i][j])
		return Matrix(res)

	def __mul__(self, other):
		res = []
		for i in range(len(self.rows)):
			row = []
			res.append(row)
			for j in range(len(other.rows[0])):
				sum = 0
				for k in range(len(self.rows[0])):
					sum = sum + self.rows[i][k] * other.rows[k][j]
				row.append(sum)
		return Matrix(res)

	def inv(self):
		A = self.copy()
		B = matrix_I(self.size())
		I = []
		J = []
		bk = True
		cntRow = 0
		cntCol = 0
		n = len(self.rows)
		for k in range(n):
			if not bk:
				break;
			if k not in I:
				I.append(k)
				cntRow += 1
				bl = True
				for l in range(n):
					if not bl:
						break;
					if l not in J:
						a = A[k][l]
						if a != 0:
							J.append(l)
							cntCol += 1
							bl = False
							for p in range(n):
								if p != k:
									tmp = A[p][l]
									for q in range(n):
										A[p][q] = A[p][q] - A[k][q]*tmp/a
										B[p][q] = B[p][q] - B[k][q]*tmp/a
				if cntRow != cntCol:
					return None;
		for l in range(n):
			for k in range(n):
				a = A[k][l]
				if a != 0:
					A[k][l] = 1
					for p in range(n):
						B[k][p] = B[k][p]/a
					if k != l:
						A.exchange_row(k, l)
						B.exchange_row(k, l)
					break;
		return B

	def exchange_row(self, k, l):
		for j in range(len(self.rows)):
			tmp = self[k][j]
			M[k][j] = M[l][j]
			M[l][j] = tmp

	def transpose(self):
		res = []
		for i in range(len(self.rows[0])):
			row = []
			res.append(row)
			for j in range(len(self.rows)):
				row.append(self.rows[j][i])
		return Matrix(res)

	def size(self):
		return (len(self.rows), len(self.rows[0]))

	def __getitem__(self, i):
		return self.rows[i]

	def __str__(self):
		return str(self.rows)

def matrix_I(sizes):
	(rows, columns) = sizes
	res = []
	for i in range(rows):
		row = []
		res.append(row)
		for j in range(columns):
			if i == j:
				row.append(1.0)
			else:
				row.append(0)
	return Matrix(res)
